package week3;

import base.TreeNode;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 *
 * 236. 二叉树的最近公共祖先
 * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
 *
 * 执行结果：  通过  显示详情
 *
 * 添加备注
 * 执行用时：11 ms, 在所有 Java 提交中击败了15.04% 的用户
 * 内存消耗：41.4 MB, 在所有 Java 提交中击败了5.29% 的用户
 */
public class Week3LowestCommonAncestorOfABinaryTree {



    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        Map<Integer, TreeNode> valueNodeMap = new HashMap<Integer, TreeNode>(); // 值节点
        Set<Integer> visitSet = new HashSet<Integer>(); // 访问过的节点

        dfs(root, valueNodeMap);  // 从 root 节点开始 存储所有节点值
        for(; p != null; ) {
            visitSet.add(p.val);
            p = valueNodeMap.get(p.val);
        }
        for(; q != null;) {
            if(visitSet.contains(q.val)) {
                return q;
            }
            q = valueNodeMap.get(q.val);
        }
        return null;

    }

    public void dfs(TreeNode node, Map<Integer, TreeNode> valueNodeMap) {
        if(node.left != null) {
            valueNodeMap.put(node.left.val, node);
            dfs(node.left, valueNodeMap);
        }
        if(node.right != null) {
            valueNodeMap.put(node.right.val, node);
            dfs(node.right, valueNodeMap);
        }
    }

}
